package xyf.p05.heap_trie;

import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * ClassName: P0313_UglyNumber
 * Description:
 * Author: xyf
 * Date: 9/23/22 9:04 PM
 * Version: 1.0
 **/
public class P0313_UglyNumber
{
    public int nthSuperUglyNumber(int n, int[] primes)
    {
        // 优先级队列（⼩顶堆）
        PriorityQueue<Long> pq = new PriorityQueue<>(
                new Comparator<Long>()
                {
                    public int compare(Long o1, Long o2)
                    {
                        if (o1 < o2) return -1;
                        else if (o1 == o2) return 0;
                        else return 1;
                    }
                });
        // 先将primes放进去
        pq.add(1L);
        // 避免重复
        long lastData = -1;
        int k = 0;
        while (!pq.isEmpty() && k < n)
        {
            long data = pq.poll();
            if (data == lastData)
            {
                continue;
            }
            k++;
            lastData = data;
            // 扩展
            for (int i = 0; i < primes.length; ++i)
            {
                pq.add(data * primes[i]);
            }
        }
        return (int) lastData;
    }
}